package 剑指Offer专项突破;

/**
 * 二分专场，栽在这里一次(旋转数组)
 */
public class Algo68 {
    public static void main(String[] args) {
        System.out.println(singleNonDuplicate1(new int[]{3,3,7,7,10,11,11}));
    }


    /**
     * 唯一的数字
     * @param nums
     * @return
     */
    public static int singleNonDuplicate1(int[] nums) {
        if(nums.length == 1 ) {
            return nums[0];
        }
        //偶数下标开始，奇数结束
        int l = 0;
        int r = nums.length-1;
        while (l<=r) {
            int mid = l + (r-l)/2;
            if(mid%2==0) {
                if(mid+1<nums.length && nums[mid+1] == nums[mid]) {
                    l = mid+1;
                }else if(mid - 1>=0 && nums[mid-1] != nums[mid]) {
                    return nums[mid];
                }else {
                    r = mid-1;
                }
            }else {
                if( nums[mid-1] == nums[mid]) {
                    l = mid+1;
                }else if(mid+1<nums.length && nums[mid+1] != nums[mid]){
                    return nums[mid];
                }else {
                    r = mid-1;
                }
            }
        }
        return nums[0];
    }


    /**
     * 069 山峰数组的顶部下标
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray1(int[] arr) {
        int l = 0;
        int r = arr.length-1;

        while (l<=r) {
            int mid = l + (r-l)/2;
            if(mid - 1 >=0 ) {
                if(arr[mid]>arr[mid-1]) {
                    if(mid+1 <arr.length && arr[mid]> arr[mid+1]) {
                        return mid;
                    }
                }else if(arr[mid]<arr[mid-1]) {
                    r = mid-1;
                    continue;
                }

                l = mid+1;
            }else if(mid+1 <arr.length) {
                if( arr[mid]> arr[mid+1] ) {
                        return mid;
                }else if(arr[mid] < arr[mid+1]) {
                    l = mid+1;
                    continue;
                }
                r = mid-1;
            }
        }
        return 0;
    }


    /**
     * 068 O(logN) 查找插入位置
     * 看到 O(logN)  二分查找、 先排序等等都要想一想
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert1(int[] nums, int target) {
        //题目已经排好序了
        if(nums.length == 0 || target<=nums[0]) {
            return 0;
        }

        if(target>nums[nums.length-1]) {
            return nums.length;
        }

        int left = 0;
        int right = nums.length-1;

        while (left<=right) {
            int mid =left + (right - left) /2;
            if(nums[mid] > target) {
                if(mid - 1 >=0 && nums[mid-1] <target) {
                    return mid;
                }
                right = mid-1;
            }else if(nums[mid]<=target) {
                if (nums[mid] == target) {
                    return mid;
                }
                if(mid+1<nums.length && nums[mid+1] > target) {
                    return mid+1;
                }
                left = mid+1;
            }
        }
        return nums.length;
    }

    /**
     * 查找一个排序数组，有就返回下标，没有返回应该插入的下标
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left<=right) {
            int mid = (left+right)/2;
            if(nums[mid]>=target) {
                if(mid == 0 || nums[mid-1] < target) {
                    return mid;
                }
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return nums.length-1;
    }

    /**
     * Offer69 山峰数组的顶部
     * 这道题的启示是：  left从1开始， right从length-2开始，可以省去 mid==0 mid==lengt-1判断
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray(int[] arr) {
        //
        int left = 1;
        int right = arr.length-2;
        while (left<=right) {
            int mid = (left+right)/2;
            if(arr[mid]> arr[mid-1] && arr[mid]>arr[mid+1]) {
                return mid;
            }
            if(arr[mid-1] < arr[mid] && arr[mid]<arr[mid+1]) {
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return -1;
    }

    /** todo 【Delay】
     * Offer70  排序数组中只出现一次的数字
     * 1、有一个直观的解法是异或
     *          int num = 0;
     *         for (int i = 0; i < nums.length; i++) {
     *             num ^= nums[i];
     *         }
     *         return num;
     *
     * 2、如果是排序的，那么想到二分查找
     * 排序数组，i和i+1成对出现
     * i为偶数
     * i+1为奇数
     * @param nums
     * @return
     */
    public static int singleNonDuplicate(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if(mid%2==0) {
                if(nums[mid] == nums[mid+1]) {
                    //在mid后面
                    l = mid+1;
                }else {
                    //判断是否是第一个
                    if(nums[mid] != nums[mid-1]) {
                        return mid;
                    }
                    r = mid-1;
                }
            }else {
                if(nums[mid] == nums[mid-1]) {
                    //在mid后面
                    l = mid-1;
                }else {
                    if(nums[mid-1] != nums[mid-2]) {
                        return mid;
                    }
                    r = mid+1;
                }
            }
        }
        return -1;
    }
}
